package 数组.middle;

import sun.awt.image.ImageWatched;

import java.util.*;

/**
 * @author Lw中
 * @date 2021/7/21 21:45
 */
public class ShiWu {

    // 15. 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        // 方法一：暴力拆解，超出时间限制
//        List<List<Integer>> results = new LinkedList<>();
//        //排序
//        Arrays.sort(nums);
//        for(int i = 0; i < nums.length - 2; i++){
//            int x = nums[i];
//            //去重，假如给的用例是[0, 0, 0, 0],当i第一次遇到0时，为首次遇见没有关系，可如果这次i的循环结束了
//            //i+1进入第二次循环，那么这时候还是遇到0，为连续的第二次遇见，这就造成了前后重复，必须要跳过
//            if(i > 0 && nums[i - 1] == nums[i]) continue;
//            for(int j = i + 1; j < nums.length - 1; j++){
//                int y = nums[j];
//                //去重原理同i，j必须大于i + 1，因为j是从i + 1开始的，假如这时开始就后退一步，就去到i的地盘了
//                if(j > i + 1 && nums[j - 1] == nums[j]) continue;
//                for(int k = j + 1; k < nums.length; k++){
//                    int z = nums[k];
//                    //去重原理同j
//                    if(k > j + 1 && nums[k - 1] == nums[k]) continue;
//                    if(x + y + z == 0){
//                        List<Integer> list = new LinkedList<Integer>();
//                        list.add(x);
//                        list.add(y);
//                        list.add(z);
//                        results.add(list);
//                    }
//                }
//            }
//        }
//        return results;
        // 方法二：使用map将一个数存储起来，然后在进行两次循环
        List<List<Integer>> list = new LinkedList<>();
        Map<Integer, Integer> map = new HashMap<>();
        Arrays.sort(nums);
        // 使用map将一个数进行存储
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length - 2; i++) {
            int x = nums[i];
            // 如果第一个数就大于0就跳出这次循环进入下次循环
            if (x > 0) break;
            // 去重
            if (i > 0 && nums[i - 1] == x) continue;
            for (int j = i + 1; j < nums.length - 1; j++) {
                int y = nums[j];
                // 如果前两个数之和大于0就跳出此次循环进入下一次循环
                if (x + y > 0) break;
                if (j > i + 1 && nums[j - 1] == y) continue;
                // 计算出第三个数是什么时三数之和为零
                int z = 0 - x - y;
                // 判断map中是否存在这个key，并且判断这个key的value值（排序之后的下标）是否大于j
                if (map.containsKey(z) && map.get(z) > j) {
                    List<Integer> list1 = new LinkedList<>();
                    list1.add(x);
                    list1.add(y);
                    list1.add(z);
                    list.add(list1);
                }
            }
        }
        return list;

        // 方法三：使用双指针（将nums排序之后，循环遍历nums数组，使用两个数组，在数组尾（rear）和遍历中数组元素后面的元素（）font）
    }


}
